package cn.xkai.exercise.a;

import com.google.gson.Gson;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @description: 杨辉三角Ⅱ
 * 自己的思路：不再把得到的层级添加到集合，而是覆盖集合，最后得到的结果就是指定层级
 * 借鉴的思路：临时2个临时变量记录杨辉三角上一层对应的2个值
 * 心得：认值读题，O(rowIndex)的空间复杂度
 * @author: kaixiang
 * @date: 2022-06-28
 **/
public class Solution19 {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> list = Collections.singletonList(1);
        for (int i = 1; i < rowIndex + 1; i++) {
            List<Integer> subList = new ArrayList<>();
            for (int j = 0; j < i + 1; j++) {
                if (j == 0 || j == i) {
                    subList.add(1);
                    continue;
                }
                subList.add(list.get(j - 1) + list.get(j));
            }
            list = subList;
        }
        return list;
    }

    public List<Integer> getRowRefer(int rowIndex) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        int left, right;
        for (int i = 1; i < rowIndex + 1; i++) {
            list.add(1);
            left = 1;
            for (int j = 1; j < i; j++) {
                right = list.get(j);
                list.set(j, left + right);
                left = right;
            }
        }
        return list;
    }

    public static void main(String[] args) {
        int rowIndex = 3;
        Solution19 solution19 = new Solution19();
        System.out.println(new Gson().toJson(solution19.getRow(rowIndex)));
    }
}
